#include <bits/stdc++.h>
using namespace std;
class LRUCache {
  int cap, sz;
  struct Node {
    int key, val;
    Node *prev, *next;
  } *head, *tail;
  vector<Node*> nodes;

  void insert_first(Node *node) {
    Node* nxt = head->next;
    node->next = nxt;
    node->prev = head;
    head->next = node;
    nxt->prev = node;
  }
  void remove(Node *node) {
    Node* pre = node->prev, *nxt = node->next;
    pre->next = nxt;
    nxt->prev = pre;
  }
public:
  LRUCache(int capacity) {
    nodes.resize(100001);
    cap = capacity;
    head = new Node{0, 0, 0, 0};
    tail = new Node{0, 0, head, 0};
    head->next = tail;
    sz = 0;
  }
  
  int get(int key) {
    if (nodes[key]) {
      Node *node = nodes[key];
      remove(node);
      insert_first(node);
      return node->val;
    }
    return -1;
  }
  
  void put(int key, int value) {
    if (!nodes[key]) {
      Node* new_node = new Node{key, value, 0, 0};
      insert_first(new_node);
      nodes[key] = new_node;
      sz ++;
      if (sz > cap) {
        sz --;
        Node *node = tail->prev;
        nodes[node->key] = 0;
        remove(node);
      }
    } else {
      Node* node = nodes[key];
      node->val = value;
      remove(node);
      insert_first(node);
    }
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */